package org.everyday;

/**
 * @version v1.0.0
 * 创建时间：2022/7/11 10:14
 */
public class L676 {
    Trie root;
    public L676() {
        root = new Trie();
    }
    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            Trie cur = root;
            for (int i = 0; i < word.length(); ++i) {
                char ch = word.charAt(i);
                int idx = ch - 'a';
                if (cur.child[idx] == null) {
                    cur.child[idx] = new Trie();
                }
                cur = cur.child[idx];
            }
            cur.isFinished = true;
        }
    }

    public boolean search(String searchWord) {
        return dfs(searchWord, root, 0, false);
    }

    private boolean dfs(String searchWord, Trie node, int pos, boolean modified) {
        if (pos == searchWord.length()) {
            return modified && node.isFinished;
        }
        int idx = searchWord.charAt(pos) - 'a';
        // 不为空的情况，全量利用前缀树，匹配build时没有刚好差一个字符的情况
        if (node.child[idx] != null && dfs(searchWord, node.child[idx], pos + 1, modified)) {
            return true;
        }
        // 匹配build时刚好差一个字符的情况，此时只要没有修改过都要尝试修改，（例如：hello和hallo，search hello）
        if (!modified){
            for(int i=0;i<26;i++){
                // pos位置替换任意一个是node上不是pos的字符
                if(idx != i && node.child[i] != null && dfs(searchWord,node.child[i],pos+1,true)){
                    return true;
                }
            }
            // return false;//第二次走不到
        }
        return false;
    }

    public static void main(String[] args) {
        L676 l676 = new L676();
        l676.buildDict( new String[]{"hello","leetcode"});
        l676.search("hello");
    }
}
class Trie {
    boolean isFinished;
    Trie[] child;
    public Trie() {
        isFinished = false;
        child = new Trie[26];
    }
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dictionary);
 * boolean param_2 = obj.search(searchWord);
 */